כל פקודה תתחיל ב-MKגדולות עש מיכאל קלי (Michael Kali), וזאת משתי סיבות:
כדי שבטבלת הקיצורים שבתוך \SpecialChar LyX תופענה כל הפקודות זו לצד זו.
הבחירה דווקא באותיות גדולות נועדה לוודא שהפקודות אינן מתנגשות עם פקודות \SpecialChar LaTeX מקוריות.
על הפקודות להיות קצרות ככל האפשר, וזאת כדי לאפשר את כתיבתן במהירות מבלי ליצור להן קיצור מקלדת. הסיבה לכך שלא ניצור קיצור מקלדת לכל פקודה היא שפעמים רבות ניצור פקודות שתיועדנה למקרים מסוימים מאוד, ואז יעבור זמן רב עד שנשתמש בקיצור המקלדת בפעם הבאה ולכן לא נזכור אותו - הרבה יותר פשוט לזכור את הפקודה שיצרנו מכיוון שיש לה תוכן אמיתי שקשור לפלט הרצוי מן הפקודה. סיבה נוספת היא שיצירת קיצור מקלדת לכל פקודה ולו החריגה ביותר תקשה עלינו ליצור קיצורי מקלדת לפקודות חשובות יותר. לפיכך פקודות שימושיות מאוד שבוודאי ניצור להן קיצור מקלדת ונשתמש בו פעמים רבות אינן צריכות להיות קצרות.
כדי להקל על כתיבת פקודות שלא יצרתי להן קיצור מקלדת כתבתי קיצור מקלדת שיוצר את הקידומת של כל פקודות ה-macrosשלי ואז כל מה שנותר הוא להקיש שלוש-ארבע אותיות כדי לבחור את הפקודה הרצויה, קיצור המקלדת המדובר הוא "Ctrl+k".
לכל גופן יש קידומת בת שתי אותיות.
\(\:\)
\(\:\)קבוצות ופונקציות לפי קורסיםLatexCommand ruleoffset "0.5ex"width "100col%"height "1pt"\(\:\)
\(\:\)המספרים המרוכבים ופונקציות מרוכבות\(\:\)
\(\newcommand{\MKcis}{\text{cis}}\)\(\cos+i\cdot\sin\). המספרים המרוכבים.
\(\newcommand{\MKre}{\text{Re}}\)החלק הממשי של מספר מרוכב. המספרים המרוכבים.
\(\newcommand{\MKim}{\text{Im}}\)החלק המדומה של מספר מרוכב. המספרים המרוכבים.מופיע גם כתמונה של פונקציה.
הגדרה 1.1. גרף לא מכוון תהא \(V\) קבוצה סופית ולא ריקה ותהא \(E\subseteq P\left(V\right)\) כך שלכל \(e\in E\) מתקיים \(\left|e\right|=2\), הזוג \(G:=\left(V,E\right)\) הוא גרף לא מכוון.
הגדרה 1.2. גרף מכוון תהא \(V\) קבוצה סופית ולא ריקה ותהא \(E\subseteq V\times V\), הזוג \(G:=\left(V,E\right)\) הוא גרף מכוון.
הגדרה 1.3. יהי \(G:=\left(V,E\right)\) גרף (מכוון/לא מכוון), איברי \(V\) נקראים קודקודים או צמתים ואיברי \(E\) נקראים צלעות או קשתות.
יהי \(G:=\left(V,E\right)\) גרף.
עבור גרף לא מכוון
נניח ש-\(G\) אינו מכוון.
הגדרה 1.4. נאמר ש-\(G\) הוא גרף שלם אם \(E=\left\{ e\in P\left(V\right):\left|e\right|=2\right\} \), הגרף השלם מגודל \(n\in\MKnatural\) מסומן ב-\(K_{n}\).
מסקנה 1.5. לכל \(n\in\MKnatural\), מספר הצלעות ב-\(K_{n}\) הוא \(\sum_{i=1}^{n-1}i=\frac{n^{2}-n}{2}={n \choose 2}\).
הגדרה 1.6. הגרף המשלים של \(G\) הוא \(\overline{G}:=\left(V,\overline{E}\right)\) כאשר \(\overline{E}:=\left\{ e\in P\left(V\right):\left|e\right|=2,\ e\notin E\right\} \).
הגדרה 1.7. נאמר שקודקוד \(u\in V\) הוא שכן של קודקוד \(v\in V\) אם \(\left\{ v,u\right\} \in V\).
מסקנה 1.8. לכל שני קודקודים \(v,u\in V\): \(u\) הוא שכן של \(v\) אם"ם \(v\) הוא שכן של \(u\).
הגדרה 1.9. הדרגה של קודקוד \(v\in V\) היא \(d\left(v\right):=\left|\left\{ e\in E:v\in e\right\} \right|\), כלומר הדרגה היא מספר השכנים של הקודקוד (ששווה למספר הצלעות שבהן הוא מופיע).
הגדרה 1.10. נאמר שקודקוד \(v\in V\) הוא עלה אם \(d\left(v\right)=1\).
הגדרה 1.11. נאמר ש-\(G\) הוא \(d\)-רגולרי (וגם באופן כללי גרף רגולרי) אם לכל \(v,u\in V\) מתקיים \(d\left(v\right)=d=d\left(u\right)\) (עבור \(d\in\MKnatural_{0}\) כלשהו).
עבור גרף מכוון
נניח ש-\(G\) מכוון.
הגדרה 1.12. \(\:\)
דרגת היציאה של קודקוד \(v\in V\) היא \(\MKdout\left(v\right):=\left|\left\{ \left(v,u\right)\in E:u\in V\right\} \right|\). כלומר דרגת היציאה של קודקוד היא מספר הצלעות היוצאות ממנו (אלו שבהן הוא מופיע ראשון).
דרגת הכניסה של קודקוד \(v\in V\) היא \(\MKdin\left(v\right):=\left|\left\{ \left(u,v\right)\in E:u\in V\right\} \right|\). כלומר דרגת הכניסה של קודקוד היא מספר הצלעות הנכנסות אליו (אלו שבהן הוא מופיע שני).
הדרגה של קודדקוד \(v\in V\) היא \(d\left(v\right):=\MKdin\left(v\right)+\MKdout\left(v\right)\). כלומר הדרגה של קודקוד היא מספר הצלעות המחוברות אליו ללא קשר לכיוונן (אלו שבהן הוא מופיע).
הגדרה 1.13. נאמר שקודקוד \(u\in V\) הוא שכן של קודקוד \(v\in V\) אם \(\left(v,u\right)\in V\).
1.2 טענות בסיסיות
\(\clubsuit\)
הטענה הבאה (והמסקנה שבעקבותיה
טענה 1.14. יהיו \(\MKseq v,n\) כל הקודקודים ב-\(V\) (\(n:=\left|V\right|\)). מתקיים:\[
\sum_{i=1}^{n}d\left(v_{i}\right)=2\cdot\left|E\right|
\]בפרט, סכום דרגות הקודקודים של כל גרף הוא זוגי.
מסקנה 1.15. מספר הקודקודים ב-\(G\) שדרגתם אי-זוגית הוא אי-זוגי.
2 מסלולים וקשירות
יהי \(G:=\left(V,E\right)\) גרף.
2.1 מסלולים
הגדרה 2.1. \(\:\)
נניח ש-\(G\) אינו מכוון; נאמר שסדרת קודקודים \(\left(\MKseq v,n\right)\) היא מסלול, אם \(\left\{ v_{i},v_{i+1}\right\} \in E\) לכל \(n-1\geq i\in\MKnatural\).
נניח ש-\(G\) מכוון; נאמר שסדרת קודקודים \(\left(\MKseq v,n\right)\) היא מסלול, אם \(\left\{ v_{i},v_{i+1}\right\} \in E\) לכל \(n-1\geq i\in\MKnatural\).
יהי \(p:=\left(\MKseq v,n\right)\) מסלול ב-\(G\).
הגדרה 2.2. \(\:\)
\(p\) ייקרא פשוט אם אין בו חזרה על קודקוד פעמיים - כלומר לכל \(n\geq i,j\in\MKnatural\) כך ש-\(i\neq j\) מתקיים \(v_{i}\neq v_{j}\).
\(p\) ייקרא גם מסילה אם אין בו חזרה על צלע אחת פעמיים - כלומר לכל \(n>i,j\in\MKnatural\) כך ש-\(i\neq j\) מתקיים \(\left\{ v_{i},v_{i+1}\right\} \neq\left\{ v_{j},v_{j+1}\right\} \) (אם \(G\) לא מכוון) או \(\left(v_{i},v_{i+1}\right)\neq\left(v_{j},v_{j+1}\right)\) (אם \(G\) מכוון).
\(p\) ייקרא מסילה פשוטה אם הוא מסילה, ובנוסף הוא גם מסלול פשוט.
\(p\) ייקרא מעגל אם \(v_{1}=v_{n}\).
\(p\) ייקרא מעגל פשוט אם הוא מעגל, ובנוסף המסלול \(\left(\MKseq v,{n-1}\right)\) הוא מסלול פשוט1כלומר אין ב-\(p\) חזרה על קודקוד פעמיים, למעט החזרה המובנית על הקודקוד הראשון..
מסקנה 2.3. \(p\) הוא מסלול פשוט אם"ם \(p\) הוא מסילה פשוטה.
מסקנה 2.4. אם \(p\) הוא מעגל אז קיים \(n\geq k\in\MKnatural\) כך ש-\(\left(\MKseq v,k\right)\) הוא מעגל פשוט.
טענה 2.5. נניח ש-\(G\) לא מכוון, אם \(\left|E\right|\geq\left|V\right|\) אז יש ב-\(G\) מעגל פשוט.
2.2 קשירות
הגדרה 2.6. \(\:\)
נאמר ש-\(G\)קשיר (בגרפים מכוונים גם: קשיר באופן חזק) אם לכל שני קודקודים \(v,u\in V\) קיים מסלול המחבר ביניהם2כלומר קיים מסלול שהם נמצאים בקצותיו..
קבוצה \(S\subseteq V\) תיקרא קשירה (בגרפים מכוונים גם: קשירה באופן חזק), אם הגרף \(\left(S,E\cap S^{2}\right)\) קשיר.
קבוצה \(S\subseteq V\) תיקרא רכיב קשירות של \(G\) (בגרפים מכוונים גם: רכיב קשירות חזקה), אם לכל קבוצה קשירה \(S'\subseteq V\) כך ש-\(S\subseteq S'\) מתקיים \(S=S'\).
מסקנה 2.7. \(\:\)
\(G\) קשיר אם"ם ל-\(G\) יש רכיב קשירות יחיד.
\(V\) היא איחוד זר של רכיבי הקשירות ב-\(G\).
טענה 2.8. מספר רכיבי הקשירות של \(G\) גדול או שווה ל-\(\left|V\right|-\left|E\right|\); בפרט, אם \(G\) קשיר אז \(\left|E\right|\geq\left|V\right|-1\).
2.3 מסלול המילטון ומסילת אוילר
הגדרה 2.9. \(\:\)
\(p\) ייקרא מסלול המילטון3ערך בוויקיפדיה: ויליאם ריאן המילטון. (או מסילת המילטון), אם לכל \(v\in V\) קיים \(n\geq i\in\MKnatural\) כך ש-\(v=v_{i}\).
\(p\) ייקרא מעגל המילטון אם הוא מעגל, ובנוסף הוא גם מסלול המילטון.
\(p\) ייקרא מסילת אוילר (וגם מסלול אוילר) אם הוא מסילה, ובנוסף לכל \(e\in E\) קיים \(n>i\in\MKnatural\) כך ש-\(e=\left\{ v_{i},v_{i+1}\right\} \) (בגרפים לא מכוונים) או \(e=\left(v_{i},v_{i+1}\right)\) (בגרפים מכוונים).
\(p\) ייקרא מעגל אוילר אם הוא מעגל, ובנוסף הוא גם מסילת אוילר.
\(\clubsuit\)
נכון להיום אין בנמצא אלגוריתם יעיל הקובע לכל גרף אם יש בו מעגל המילטון, וכנראה שגם לא יהיה, שכן בעיה זו היא בעייתNP-שלמה ולכן קיום של פתרון יעיל עבורה (אלגוריתם בעל זמן ריצה פולינומיאלי) יגרור ש-P=NP.
אם יש ב-\(G\) מסילת אוילר אז דרגתו של כל אחד מן הקודקודים זוגית או שיש בדיוק שני קודקודים שדרגתם אי-זוגית.
יש ב-\(G\) מעגל אוילר אם"ם \(G\) קשיר דרגתו של כל אחד מן הקודקודים זוגית.
משפט 2.11. נניח ש-\(G\) מכוון.
אם יש ב-\(G\) מסילת אוילר אז מתקיימת אחת משתי האפשרויות הבאות:
לכל \(v\in V\) מתקיים \(\MKdin\left(v\right)=\MKdout\left(v\right)\).
קיימים בדיוק שני קודקודים \(v,u\in V\) שדרגת היציאה שלהם שונה מדרגת הכניסה, ועבורם מתקיים \(\MKdin\left(v\right)=\MKdout\left(v\right)+1\) ו-\(\MKdout\left(v\right)=\MKdin\left(u\right)+1\).
יש ב-\(G\) מעגל אוילר אם"ם \(G\) קשיר ולכל \(v\in V\) מתקיים \(\MKdin\left(v\right)=\MKdout\left(v\right)\).
3 עצים
הגדרה 3.1. \(\:\)
גרף לא מכוון ייקרא עץ אם הוא קשיר וחסר מעגלים פשוטים4שקול לחסר מעגלים..
גרף מכוון ייקרא עץ אם הוא קשיר, חסר מעגלים, ובנוסף דרגת הכניסה של כל קודקוד קטנה או שווה ל-\(1\).
טענה 3.2. בכל עץ יש עלה.
מסקנה 3.3. בכל עץ בעל שני קודקודים ומעלה יש שני עלים.
יהי \(G:=\left(V,E\right)\) גרף לא מכוון.
טענה 3.4. אם \(G\) הוא עץ אז \(\left|E\right|=\left|V\right|-1\).
\(\clubsuit\)
מכאן, ע"פ טענה 2.9, שעץ הוא גרף קשיר בעל מספר צלעות מינימלי.
\(\clubsuit\)
מכאן ע"פ טענה 3.4, שעץ הוא גרף חסר מעגלים בעל מספר צלעות מקסימלי.
\(\clubsuit\)
בפרט אם \(\left|E\right|=\left|V\right|-1\) ומתקיים אחד משני התנאים האחרים אז \(G\) הוא עץ.
טענה 3.5. אם \(G\) קשיר, ובנוסף \(\left|E\right|=\left|V\right|-1\), אז אין ב-\(G\) מעגל פשוט (כלומר \(G\) הוא עץ).
מסקנה 3.6. נניח ש-\(G\) קשיר, ב-\(G\) יש מעגל פשוט אם"ם \(\left|E\right|\geq\left|V\right|\).
למה 3.7. אם \(G\) קשיר, ובנוסף מסלול \(\left(v_{1},v_{2},\ldots,v_{n}\right)\) ב-\(G\) הוא מעגל, אז גם הגרף \(\left(V,E\setminus\left\{ v_{1},v_{2}\right\} \right)\) קשיר.
מסקנה 3.8. יהי \(G:=\left(V,E\right)\) גרף, כל שניים מהתנאים הבאים גוררים את השלישי:
\(G\) קשיר.
\(G\) חסר מעגלים פשוטים5שקול לחסר מעגלים..
מתקיים \(\left|E\right|=\left|V\right|-1\).
הגדרה 3.9. \(G\) ייקרא יער אם אין בו מעגלים.
מסקנה 3.10. \(G\) הוא יער אם"ם כל רכיב קשירות שלו הוא עץ.
4 תורת רמזי
יהי \(G:=\left(V,E\right)\) גרף לא מכוון.
הגדרה 4.1. צביעה של \(G\) היא פונקציה מ-\(E\) לקבוצת צבעים נתונה \(\left\{ c_{1},c_{2},\ldots,c_{n}\right\} \).
טענה 4.2. יהיו \(2\leq n,m\in\MKnatural\), אם קיימים \(a,b\in\MKnatural\) כך שמתקיים:
ב-\(K_{a}\) הצבוע באדום וכחול יש בהכרח תת-גרף \(K_{n}\) הצבוע כולו אדום ו/או תת-גרף \(K_{m-1}\) הצבוע כולו כחול.
ב-\(K_{b}\) הצבוע באדום וכחול יש בהכרח תת-גרף \(K_{n-1}\) הצבוע כולו אדום ו/או תת-גרף \(K_{m}\) הצבוע כולו כחול.
אז ב-\(K_{a+b}\) הצבוע באדום וכחול יש בהכרח תת-גרף \(K_{n}\) הצבוע כולו אדום ו/או \(K_{m}\) הצבוע כולו כחול.
יהי \(v\in V\), מהגדרת \(K_{a+b}\) מתקיים \(d\left(v\right)=a+b-1\) ולכן מעקרון שובך היונים נובע שאחד מן השניים מתקיים:
מקרה1: יש לפחות \(a\) צלעות ב-\(E\) הכוללות את \(v\) וצבועות כולן בכחול.
מקרה2: יש לפחות \(b\) צלעות ב-\(E\) הכוללות את \(v\) וצבועות כולן באדום.
במקרה1נתבונן ב-\(K_{a}\)המורכב מהקודקודים המתאימים, ע"פ הנתון יש בו \(K_{n}\) הצבוע כולו אדום (וסיימנו) או שיש בו \(K_{m-1}\) הצבוע כולו כחול (ואז נצרף אליו את \(v\) ונקבל \(K_{m}\)כחול וסיימנו).
במקרה2נתבונן ב-\(K_{b}\)המורכב מהקודקודים המתאימים, ע"פ הנתון יש בו יש בו \(K_{m}\) הצבוע כולו כחול (וסיימנו) או שיש בו \(K_{n-1}\) הצבוע כולו אדום (ואז נצרף אליו את \(v\) ונקבל \(K_{n}\)אדום וסיימנו).
משפט 4.4. משפט רמזי6ערך בוויקיפדיה: פרנק רמזי. יהיו \(2\leq n,m\in\MKnatural\), נסמן \(N:={n+m-2 \choose n-1}\) ויהי \(K_{N}\) כשהוא צבוע באדום וכחול, יש ב-\(K_{N}\) תת-גרף \(K_{n}\) שכולו צבוע אדום ו/או שיש ב-\(K_{N}\) תת-גרף \(K_{m}\) שכולו צבוע כחול.
הוכחה. נוכיח את הטענה באינדוקציה על \(n+m\).
בסיס האינדוקציה:\(n+m=4\) ומכאן ש-\(n=m=2\) ו-\(N:={2+2-2 \choose 2-1}={2 \choose 1}=2\) ואכן ב-\(K_{2}\) יש רק צלע אחת וממילא הוא מקיים שיש בו תת-גרף \(K_{2}\) הצבוע כולו באותו צבע (אדום/כחול).
צעד האינדוקציה: יהי \(4\leq k\in\MKnatural\) ונניח שלכל \(2\leq a,b\in\MKnatural\) המקיימים \(k=a+b\) יש ב-\(K_{N}\)7כאשר \(N:={a+b-2 \choose a-1}\). (כשהוא צבוע אדום וכחול) תת-גרף \(K_{a}\)צבוע כולו אדום ו/או שיש בו תת-גרף \(K_{b}\) הצבוע כולו כחול.
יהיו \(2\leq n.m\in\MKnatural\) כך ש-\(k+1=n+m\), נשים לב שמתקיים \(k=n+\left(m-1\right)\) ו-\(k=\left(n-1\right)+m\) ונגדיר:\[
N:={n+m-2 \choose n-1}={n+m-3 \choose n-1}+{n+m-3 \choose n-2}={n+\left(m-1\right)-2 \choose n-1}+{\left(n-1\right)+m-2 \choose \left(n-1\right)-1}
\]מהנחת האינדוקציה ומהטענה הקודמת נובע שיש ב-\(K_{N}\) תת-גרף \(K_{n}\) שכולו צבוע אדום ו/או שיש ב-\(K_{N}\) תת-גרף \(K_{m}\) שכולו צבוע כחול.
מסקנה 4.5. לכל \(N<M\in\MKnatural\) ובהינתן צביעה של \(K_{M}\) באדום וכחול יש ב-\(K_{M}\) תת-גרף \(K_{n}\) שכולו צבוע אדום ו/או שיש ב-\(K_{M}\) תת-גרף \(K_{m}\) שכולו צבוע כחול.
הגדרה 4.6. מספר רמזי\(R\left(n,m\right)\) מוגדר להיות המספר הטבעי המינימלי שעבורו לכל צביעה באדום וכחול של הגרף השלם המתאים יש בו \(K_{n}\) שכולו צבוע אדום ו/או שיש בו גרף \(K_{m}\) שכולו צבוע כחול.
\(\clubsuit\)
נכון להיום אין בנמצא אלגוריתם יעיל לחישוב מספרי רמזי (!).
טענה 4.7. בהינתן צביעה של \(K_{6}\) באדום וכחול קיים ב-\(K_{6}\) תת-גרף \(K_{3}\) שכל צלעותיו צבועות באותו הצבע.
מסקנה 4.8. \(R\left(3,3\right)=6\).
טענה 4.9. לכל \(2\leq n\in\MKnatural\) מתקיים \(R\left(2,n\right)=n\).
טענה 4.10. מתקיים \(R\left(3,4\right)=9\).
טענה 4.11. לכל \(2\leq n,m\in\MKnatural\) מתקיים \(R\left(n,m\right)=R\left(m,n\right)\).
5 קוביות, גרפים דו-צדדיים וזיווגים
5.1 הגדרות
הגדרה 5.1. הקוביה ה-\(n\) מימדית היא הגרף \(Q_{n}:=\left(V,E\right)\) כאשר \(V:=\left\{ 0,1\right\} ^{n}\) ובין כל שני קודקודים השונים זה מזה בקואורדינטה אחת בדיוק מחברת צלע.
יהי \(G:=\left(V,E\right)\) גרף לא מכוון.
הגדרה 5.2. גרף דו-צדדי נאמר ש-\(G\) הוא דו-צדדי אם קיימים \(V_{1},V_{2}\subseteq V\) כך ש-\(V_{1}\cup V_{2}=V\) ו-\(V_{1}\cap V_{2}=\emptyset\) ובנוסף לכל \(e\in E\) מתקיים \(\left|V_{1}\cap e\right|=1\) (כלומר כל צלע מכילה בדיוק קודקוד אחד מ-\(V_{1}\) וקודקוד אחד מ-\(V_{2}\)), תתי-הקבוצות \(V_{1}\) ו-\(V_{2}\) נקראות הצדדים של \(G\).
הגדרה 5.3. גרף דו-צדדי שלם נאמר ש-\(G\) הוא דו-צדדי שלם אם הוא דו-צדדי וכל קודקוד בצד אחד של \(G\) הוא שכן של כל קודקוד בצד האחר, נסמן ב-\(K_{n,m}\) את הגרף הדו-צדדי השלם שצדדיו בגודל \(m\) ו-\(n\) (יש רק אחד כזה).
\(\clubsuit\)
ב-\(K_{n,m}\) מתקיים \(\left|V\right|=n+m\) ו-\(\left|E\right|=n\cdot m\).
הגדרה 5.4. נאמר ש-\(M\subseteq E\) הוא זיווג אם לכל \(e_{1},e_{2}\in M\) מתקיים \(e_{1}\cap e_{2}=\emptyset\).
הגדרה 5.5. נאמר שזיווג \(M\subseteq E\) הוא זיווג מושלם אם לכל \(v\in V\) קיימת \(e\in M\) כך ש-\(v\in e\).
הגדרה 5.6. לכל \(S\subseteq V\) נגדיר את \(N\left(S\right)\) להיות קבוצת השכנים של איברי \(S\) (יש המסמנים אותה ב-\(\Gamma\left(S\right)\)).
5.2 טענות
טענה 5.7. ב-\(Q_{n}=\left(V,E\right)\) מתקיים:
\(\left|V\right|=2^{n}\).
\(d\left(v\right)=n\) לכל \(v\in V\).
\(\left|E\right|=n\cdot2^{n-1}\).
טענה 5.8. לכל \(2\leq n\in\MKnatural\) יש ב-\(Q_{n}\) מעגל המילטון.
יהי \(G:=\left(V_{1}\cup V_{2},E\right)\) גרף דו-צדדי כאשר \(V_{1}\) ו-\(V_{2}\) הם צדדיו.
טענה 5.9. לכל מעגל \(\left(v_{0},v_{1},v_{2},\ldots,v_{n}\right)\) ב-\(G\) מתקיים \(n\in\MKeven\).
\(\clubsuit\)
זיווג מושלם בגרף דו-צדדי מגדיר פונקציה חח"ע ועל מצד אחד לצד השני, מכאן שאם יש בגרף דו-צדדי זיווג מושלם אז צדדיו באותו גודל.
בהנחה ש-\(\left|V_{1}\right|=\left|V_{2}\right|\) מתקיים: יש ב-\(G\) זיווג מושלם אם"ם \(\left|N\left(S\right)\right|\geq\left|S\right|\) לכל \(S\subseteq V_{1}\).
טענה 5.10. אם קיימים \(v,u\in V_{1}\) שדרגתם היא \(1\) וקיים \(w\in V_{2}\) כך ש-\(\left\{ w,v\right\} ,\left\{ w,u\right\} \in E\) אז אין ב-\(G\) זיווג מושלם.
טענה 5.11. לכל \(S\subseteq V_{1}\) מתקיים \(N\left(S\right)\subseteq V_{2}\).
טענה 5.12. אם יש ב-\(G\) זיווג מושלם אז לכל \(S\subseteq V_{1}\) מתקיים \(\left|N\left(S\right)\right|\geq\left|S\right|\).
משפט 5.13. משפט החתונה - משפט הול8ערך בוויקיפדיה: פיליפ הול.
אם \(\left|V_{1}\right|=\left|V_{2}\right|\) וגם לכל \(S\subseteq V_{1}\) מתקיים \(\left|N\left(S\right)\right|\geq\left|S\right|\) אז יש ב-\(G\) זיווג מושלם.
טענה 5.14. אם \(G\) הוא גם \(d\)-רגולרי (עבור \(d\in\MKnatural\) כלשהו9\(d\) בהכרח שונה מ-\(0\).) אז יש ב-\(G\) זיווג מושלם.
רוצים לפרגן לי על בניית האתר וכתיבת הסיכומים? אתם מוזמנים לתת טיפ.פורמטים נוספים:
#scrollButton {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
cursor: pointer;
background-color: #084149;
opacity: 80%;
}
#scrollImage {
position: fixed; /* Keeps the button in a fixed position */
bottom: 0.7em; /* Distance from the bottom */
right: 0.7em; /* Distance from the right */
height: 3.5em;
width: 3.5em;
opacity: 80%;
}
function scrollToTop() {
window.scrollTo({ top: 0, behavior: 'smooth' });
}
דפי האתרדף הביתאודותצור קשרמפת אתרענפים מתמטייםהתחלהאנליזהאלגברהענפים נוספיםאקסיומת השלמותסיכומי הרצאות במתמטיקהדף הביתתרומהאודותהקדשהמפת אתרהתחלהאנליזהאלגברהענפים נוספיםצור קשרעודלאתר הקודםsrayaa.comעִבְלִיקְסתנ"ך ברויאר מוקלט
( function() {
var skipLinkTarget = document.querySelector( 'main' ),
sibling,
skipLinkTargetID,
skipLink;
// Early exit if a skip-link target can't be located.
if ( ! skipLinkTarget ) {
return;
}
/*
* Get the site wrapper.
* The skip-link will be injected in the beginning of it.
*/
sibling = document.querySelector( '.wp-site-blocks' );
// Early exit if the root element was not found.
if ( ! sibling ) {
return;
}
// Get the skip-link target's ID, and generate one if it doesn't exist.
skipLinkTargetID = skipLinkTarget.id;
if ( ! skipLinkTargetID ) {
skipLinkTargetID = 'wp--skip-link--target';
skipLinkTarget.id = skipLinkTargetID;
}
// Create the skip link.
skipLink = document.createElement( 'a' );
skipLink.classList.add( 'skip-link', 'screen-reader-text' );
skipLink.href = '#' + skipLinkTargetID;
skipLink.innerHTML = 'לדלג לתוכן';
// Inject the skip link.
sibling.parentElement.insertBefore( skipLink, sibling );
}() );